// ac自动机
// https://www.luogu.com.cn/problem/P5357

int tot;
int trans[max_size][26]; // tans[u][i] = v 表示从 u 经过边 i 能到达 v，状态转移
int fail[max_size];      // 失配指针，本质上指向后缀相同的字符串的结尾节点
int cnt[max_size];       // 以该节点结尾的字符串数量
int last[max_size];      // 指向 i 的失配路径上最近的一个完整模式串的结尾节点
int visit[max_size];     // 以节点 i 结尾的模式串的查询次数
int id[max_size];        // 在节点 i 结尾的字符串是第 id[i] 个模式串
int reid[maxn];          // 第 i 个模式串在节点 reid[i] 处结尾

void init() {
    tot = 0;
    memset(trans, 0, sizeof(trans));
    memset(fail, 0, sizeof(fail));
    memset(cnt, 0, sizeof(cnt));
    memset(last, 0, sizeof(last));
    memset(visit, 0, sizeof(visit));
    memset(id, 0, sizeof(id));
}

void insert(char *s, int order = 0) { // 字典树插入
    int u = 0;
    for (int i = 0, ed = strlen(s); i < ed; ++i) {
        int &v = trans[u][s[i] - 'a'];
        if (v == 0) v = ++tot;
        u = v;
    }
    ++cnt[u];
    id[u] = order;
    reid[order] = u;
}

void build() { // 建立 ac 自动机
    queue<int> qe;
    for (int i = 0; i < 26; ++i) {
        if (trans[0][i] == 0) continue;
        int &v = trans[0][i];
        fail[v] = 0;
        last[v] = 0;
        qe.push(v);
    }
    while (!qe.empty()) {
        int u = qe.front(); // 队列中节点的 fail, last 已初始化
        qe.pop();
        for (int i = 0; i < 26; ++i) {
            if (trans[u][i] == 0) continue;
            int v = trans[u][i], p = fail[u];
            while (p > 0 && trans[p][i] == 0) // 匹配失败，指针不断倒退
                p = fail[p];
            fail[v] = trans[p][i];
            last[v] = (cnt[fail[v]] ? fail[v] : last[fail[v]]); // 路径压缩
            qe.push(v);
        }
    }
}

void ask(char *s) { // 查询 s 中，每个模式串的出现次数
    int u = 0;
    for (int i = 0, ed = strlen(s); i < ed; ++i) {
        int c = s[i] - 'a';
        while (u > 0 && trans[u][c] == 0)
            u = fail[u];
        u = trans[u][c];
        for (int v = u; v > 0; v = last[v]) {
            if (cnt[v]) visit[v]++; // 访问 fail 路径
        }
    }
}
